package __4_struction;

/*

费马vs毕达哥拉斯

计算机生成和辅助的证明和验证在计算机科学领域中占有很小的地位。四色问题的第一个证明是在计算机程序的帮助下完成的，
目前在验证方面的努力已经成功地验证了将高级代码转换到芯片级。
这个问题处理与费马大定理有关的计算量:当n > 2时，没有a^n + b*n = c*n的整数解。给定一个正整数n，
给你一个正整数N，你要写一个程序，计算关于x^2 + y*2 = z*2的解的两个量，其中x,y和z被约束为小于或等于N的正整数。
你要计算使x < y < z的三元组(x,y,z)的数量，并且它们是相对素数，也就是说，没有大于1的公因数。
您还需要计算值o < p <= n的个数，使得p不属于任何三元组(不仅仅是相对素数三元组)。

输入
输入由一个正整数序列组成，每行一个。输入文件中的每个整数将小于或等于1,000,000。输入以文件结束符结束

输出
对于输入文件中的每个整数N，打印两个以空格分隔的整数。
第一个整数是相对素数三元组的数量(使得三元组的每个组成部分都<=N)。
第二个数是<=N的正整数的个数，这些正整数不属于任何组成部分都<=N的三元组。
每个输入行应该有一个输出行。

输入示例1：
10
25
100

输出示例1：
1 4
4 9
16 27

看不懂...

 */

import java.util.Scanner;

public class Fermat_VS_Pythagoras {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int N = scan.nextInt();
            int x = 0, y = 0, z = 0;
            int sum0 = 0, sum1 = 0;
            int arr[] = new int[N+1];
            for (int i = 3; i <= N; i += 2) {
                for (int j = 1; j < i; j += 2) {
                    if (gcd(i, j) == 1) {
                        x = i * j;
                        y = (i * i - j * j) / 2;
                        z = (i * i + j * j) / 2;
                        if (z <= N) {
                            sum0++;
                            for (int l = 1; l <= N/z; l++) {
                                arr[x * l] = 1;
                                arr[y * l] = 1;
                                arr[z * l] = 1;
                            }
                        }
                    }
                }
            }
            for (int i = 1; i < N+1; i++) {
                if (arr[i] == 0) {
                    sum1++;
                }
            }
            System.out.println(sum0 + " " + sum1);
        }
    }

    private static int gcd(int i, int j) {
        // TODO Auto-generated method stub
        if (j == 0) {
            return i;
        } else {
            return gcd(j, i % j);
        }
    }

}
